'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-26 16:15:05
'''
# Definition for a binary tree node.
# OfficialSerialize 为官方二叉树的序列化方法，用以解决
# 二叉树题目的序列问题。
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class OfficialSerialize:
    def serialize(self, root):
        store = []
        re = []
        store.append(root)
        while store:
            tmp = store.pop(0)
            if not tmp:
                re.append('null')
                continue
            re.append(str(tmp.val))
            if tmp.left:
                store.append(tmp.left)
            else:
                store.append(None)
            if tmp.right:
                store.append(tmp.right)
            else:
                store.append(None)
        for i in range(len(re)-1, -1, -1):
            if re[i] == 'null':
                del(re[i])
            else:
                break
        return ','.join(re)
    
    def deserialize(self, s):
        store = []
        i = 0
        s = s.split(',')
        root=None
        if s:
            root=TreeNode(int(s[i]))
            store.append(root)
            i+=1
        while store:
            tmp = store.pop(0)
            
            if s[i] == 'null':
                tmp.left = None
            else:
                ttmp = TreeNode(int(s[i]))
                tmp.left = ttmp
                store.append(ttmp)
            i+=1
            if i>=len(s):
                break
            if s[i] == 'null':
                tmp.right = None
            else:
                ttmp = TreeNode(int(s[i]))
                tmp.right = ttmp
                store.append(ttmp)
            i+=1
            if i>=len(s):
                break
        return root


if __name__ == "__main__":
    # root = TreeNode(1)
    # tmp = TreeNode(2)
    # root.left = tmp
    # tmp2 = TreeNode(3)
    # root.right = tmp2
    # tmp = TreeNode(4)
    # tmp2.right = tmp
    null = 'null'
    root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
    for i,v in enumerate(root):
        root[i] = str(v)
    s = ','.join(root)
    # print(s)
    o_s = OfficialSerialize()
    root = o_s.deserialize(s)
    print(o_s.serialize(root))